package g06;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Main {

	private static List<State06> F = new ArrayList<State06>(); // Les états à
																// traiter
	private static List<State06> V = new ArrayList<State06>(); // Les états
																// deja traités
	private static State06 taquin;

	
	// Precondition: Le parametre taquin n'est pas null. De plus, c'est un
	// tableau carre de taille n qui represente un taquin t.
	// Postcondition: Le contenu du tableau taquin n'est pas modifie.
	// Resultat: true si le taquin t est resolvable et false si le taquin t
	// n'est pas resolvable.
	static boolean resolvable(int[][] t) {
		return min2(t) != -1;
	}

	// Precondition: Le parametre taquin n'est pas null. De plus, c'est un
	// tableau carre de taille n qui represente un taquin t qui est resolvable.
	// Postcondition: Le contenu du tableau taquin n'est pas modifie.
	// Resultat: Le nombre minimal de permutations necessaire pour resoudre la
	// taquin t.
	static int min(int[][] taquinP) {
		int [][] path = minPath(taquinP);
		return path.length;
	}
	
	static int min2(int[][] taquinP) {
		int [][] path = minPath(taquinP);
		if(path == null){
			return -1;
		} else {
			return path.length;
		}
	}
	// appelle la méthode de state06 qui renvoie les successeurs sur le State
	// passé en paramètre
	private static Stack<State06> succ(State06 f2) {
		return f2.succState(V);
	}

	private static State06 parcoursHeuristique() {
		State06 sMin = null;
		for (State06 s : F) {
			if (s.getCoutEstime() == -1) {
				s.heuristique();
			}
			if (sMin == null
					|| (sMin.getCoutEstime() + sMin.getCout()) > (s.getCout() + s
							.getCoutEstime())) {
				sMin = s;
			}
		}
		return sMin;
	}

	// Precondition: Le parametre taquin n'est pas null. De plus, c'est un
	// tableau carre de taille n qui represente un taquin t.
	// Postcondition: Le contenu du tableau taquin n'est pas modifie.
	// Resultat: Soit m le nombre minimal de permutations necessaire pour
	// resoudre la taquin t, cette methode renvoie une suite de permutations
	// legales
	// de longueur m qui permet de resoude le taquin t.
	static int[][] minPath(int[][] taquinP) {
		taquin = new State06(taquinP, 0);
		F.add(taquin);
		Stack<State06> S;
		while (!F.isEmpty()) {
			State06 f = parcoursHeuristique();
			V.add(f);
			S = succ(f);
			F.remove(f);
			F.addAll(S);
			if (f.isAGoal()) {
				return constructPath(f);
			}
		}
		return null;
	}

	private static int[][] constructPath(State06 f) {
		List<int[]> listPath = new ArrayList<int[]>();
		State06 fCurrent = f;
		do {
			if (fCurrent.getParent() == null) {
				break;
			}
			listPath.add(fCurrent.getPerm());
			fCurrent = fCurrent.getParent();
		} while (true);

		int[][] tableauPath = new int[listPath.size()][4];
		for (int i = 0; i < listPath.size(); i++) {
			tableauPath[i] = listPath.get(i);
		}
		return tableauPath;
	}
}